﻿using System;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Knapsack
{
    public class SpaceSavingKnapsackSolver : IKnapsackSolver
    {
        public double Profit(int W, IList<double> values, IList<int> weights)
        {
            var N = values.Count;
            var current = new double[W + 1];
            var previous = new double[W + 1];

            for(int n = 1; n <= N; n++)
            {
                for(int c = 0; c < weights[n-1];c++)
                {
                    current[c] = previous[c];
                }
                for(int c = weights[n-1]; c <= W; c++)
                {
                    current[c] = Math.Max(previous[c], previous[c - weights[n - 1]] + values[n - 1]);
                }
                var aux = current;
                current = previous;
                previous = aux;
            }
            return previous[W];
        }
    }
}
